A Survey of Behaviour Trees and their Applications for Game AI A Survey of Behaviour Trees and their Applications for Game AI
By Kim McQuillanvisibility
1343 Views
description
19 Pages
link1 File ▾
A Survey of Behaviour Trees
and their Applications
for Game AI
by Kim McQuillan
James Cook University
CP5330 SP2 2015
Special Interest Topic 1:
Intelligent Agents & Simulation
Word Count: 5349
Page 1 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
Abstract:
Behaviour Trees are relatively new, intuitive and versatile tools for Game Artificial
Intelligence (Game AI). While they have been utilized in the development of a few major
game releases, the commercial gaming industry is yet to harness their full potential. This
paper will examine what behaviour trees are within the context of Game AI, and provide
an overview of their potential applications within the field. It will achieve this end by
surveying a range of academic books, journal and conference papers relevant to Game
AI in general, and behaviour trees in particular. By describing the ease of use, versatility,
and potential capabilities of behaviour trees, it is hoped that this paper will help to
facilitate increased familiarity with, and further appreciation for, behaviour trees among
current and future game developers.
1. Introduction:
As games become more sophisticated, due to advances in computing power, graphics
and physics, so does the Game AI toolkit (Child & Dey, 2013). Behaviour Trees are a
relatively recent example of intuitive and versatile tools for Game AI (Kirby, 2011). While
they are beginning to be embraced commercially for some applications, their potential is
yet to be fully harnessed, with most commercial Game AI still generated by hard-coded
scripts (Černý, Plch, Marko, Gemrot, Ondráček, & Brom, 2015). This paper will examine
the nature, potential applications, benefits, limitations and trends of behaviour trees,
beginning with some general background about Game AI and decision-making.
1.1 AI for Games
1.1.1 Definition
Kirby (2011) defines Game AI as “the ability to act intelligently under changing
conditions”. While it aims to make automated decisions within a game appear intelligent,
a bigger challenge is preventing those decisions from, at times, appearing stupidity. This
is known as “avoiding artificial stupidity” (Kirby, 2011). Interestingly, even random
decisions can give a player the impression of an intelligent, ‘learning’ AI; testament that
complexity is not a goal in itself; simple systems will often suffice (Kirby, 2011).
1.1.2 Role in Game Development
A game is an entertainment product that relies on limited resources, therefore every
element should contribute to maximizing player enjoyment (Kirby, 2011). It follows that
the aim of Game AI is to enhance player experience (Johansson & Dell'Acqua, 2012). AI
actions must be noticeable to the player, else they represent no more than computational
waste (Kirby, 2011). This does not always mean the player needs to witness intelligent
behaviour at the exact moment of AI decision-making, however it should be evident at
some point, and enhance the playing experience in some way (Kirby, 2011). This could
be via realistic, appropriately stylized, or simply entertaining AI behaviours, evoking
player emotions, or simply aiding the suspension of disbelief in a game narrative.
Page 2 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
1.1.3 Approaches to Game AI
There are many different approaches to Game AI, only some of which will be highlighted
here, but all share the goal of facilitating intelligent and autonomous decision-making at
runtime (Kirby, 2011). Figure 1 (Millington & Funge, 2012) highlights the general shape of
most Game AI systems.
Figure 1: General AI model diagram
(i) Scripted AI
Scripted, or Hard-coded AI, is the most traditional approach, and still the most common.
Ranging from simple condition (if-then) statements to more object-oriented, data-driven
approaches, it can be simple, fast and effective, with minimal computational overhead
and fast execution (Kirby, 2011). As complexity grows however, the code can be
exposed as brittle, rigid, unmanageable, and a recipe for unintended artificial stupidity
(Kirby, 2011). A critical issue is the limited ability for scripted AI to assess when certain
behaviours are appropriate, particularly as size and complexity increase (Kirby, 2011).
(ii) Finite State Machines
Finite State Machines (FSM), are formal structures to address the issue of program
complexity. Figure 2 (Kirby, 2011) is a diagrammatic representation of a simple FSM for
determining NPC ‘behaviour’. The circles represent ‘states’, or behaviours, while the
arrows represent ‘transitions’ between states. The captions describe the conditions under
which transitions will occur. When using FSM it is important to review each transition to
ensure that it is “always reasonable”, since as a game progresses, contingencies can
occur which are not always obvious in the early stages of play (Kirby, 2011). Complexity
arises when the number of states ‘explodes’ to an unmanageable level, inevitably leading
to an even bigger explosion of transitions, or when multiple transitions exist out of a
single state, producing ambiguities or ‘race conditions’. Race conditions occur when the
AI system must deliberate on its next course of action due to a surfeit of ‘correct’ options
(Kirby, 2011). One way to deal with race conditions is to use a Hierarchical State
Machine (HSM), which prioritizes transitions using a stacking approach (Flórez-Puga,
Gómez-Martín, Gómez-Martín, Díaz-Agudo & González-Calero, 2009).
Figure 2: Finite State Machine Diagram
Page 3 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
(iii) Rule-based Systems
Rule-based systems consist of a set of rules and a framework to apply them (Kirby,
2011). Each time the AI “thinks”, it examines current state of the same world in
accordance with the rules. This system is less constrained than a state-based approach,
but it is difficult to plan the perfect rule for every potential scenario, and often several are
needed just to cover default behaviours (Kirby, 2011).
(iv) Random and Probabilistic Systems
Random systems can be effective in simulating real behaviour, which is occasionally
unpredictable, but only within appropriate parameters. The choice must be between
equally good options to avoid puzzling outcomes which could compromise player
experience (Kirby, 2011). Probabilistic systems consider odds in an attempt to balance
this issue of predictability versus feasibility. Methods for calculating these odds include
the popular Monte Carlo method, precomputing, and ‘faking it’, and often require some
initial guesswork to obtain numerical data, which must then be fine-tuned to perfect the
system. This ‘tuning’ is the most challenging aspect of building an effective probabilistic
system (Kirby, 2011).
(v) Machine Learning
Machine Learning, using techniques such as genetic algorithms or neural networks, is
another approach to Game AI, however to date it has not been used particularly often
outside of academic research (Kirby, 2011). Genetic algorithms are suitable for some
games, but neural networks are considered too unpredictable in many cases (Kirby,
2011). Game developers, particularly in the area of narrative games, tend to avoid
relinquishing authorial control of what happens after release, for fear of unwittingly
evoking unforeseen cases of severe artificial stupidity (Rabin, 2013).
(vi) Other Approaches
Other approaches include, but are not limited to, planning methods such as Stanford
Research Institute Problem Solver (STRIPS), Goal Oriented Action Planning (GOAP), &
Hierarchical Task Networks (HTN), pathfinding techniques such as the commonly used
A* algorithm, and Behaviour Trees, which are the focus of subsequent sections of this
paper (Kirby, 2011).
1.2 Decision -Making
Decision-making involves a character, or other game AI component, working out what to
do next, from a range of possible behaviours (Millington & Funge, 2012). The system
calculates the most appropriate behaviour at a given moment, then executes it as shown
in Figure 3 (Millington & Funge, 2012). This is the foundation of Game AI. It can be
simple, like the farm animals in Zelda games, that are stationary until a player
approaches, or complex, like enemies in Half-Life 2 that chain multiple, simultaneous
strategies into composite behaviours in order to aggressively pursue even a distant
player (Millington & Funge, 2012).
Decision making can be simple, for example. farm animals in Zelda games will stand still
unless a player approaches closely (Millington & Funge, 2012). In Half-Life 2 however,
enemies display complex decision-making by trying a number of different strategies to
reach the player, and chaining some of these actions together into composite behaviours
(Millington & Funge, 2012).
Page 4 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
Two factors affecting decision-making are selectors and reasoners (Jadon, Singhal &
Dawn, 2014). Selectors use simple logic, like selecting the first option that fits a
requirements, or by pre-determined priority. Reasoners dynamically calculate
probabilities and often select one of a number of ‘correct’ choices based on several
factors (Millington & Funge, 2012).
Section 1.1.3 of this paper outlines several different decision-making approaches, and it
important to realize they are all essentially doing the same thing – “acting intelligently
under changing conditions”, which is Kirby’s definition of Game AI (2011). Figure 4 shows
an example of a decision tree, or graphical depiction of decision-making which is simple
to read, easy to implement, and fast to execute (Millington & Funge, 2012). Decision
trees are modular, easy to create and can range from very simple to extremely
sophisticated (Millington & Funge, 2012). It is from decision trees that behaviour trees
evolved.
Figure 3: Decision Making in Game AI Figure 4: Decision Tree example
1.3 History of Behaviour Trees in Game AI
Behaviour Trees first made a splash as the ‘next big thing’ at the 2005 Game Developers
Conference (Kirby, 2011). They had already been used in Halo 2 (2004), made another
appearance in in Spore (2008), and began to gain ground towards acceptance as a
mainstream approach for non-player character (NPC) AI. It was not, however, until
Champanard’s (2012) video tutorial on second generation behaviour trees, for
aigamedev.com, that stakeholders began to recognize the magnitude of untapped
potential for behaviour trees. Since then, despite slow (but steady) progress in
commercial game AI, particularly in relation to NPCs, much promising research has been
undertaken into utilizing behaviour trees for several other Game AI applications, as well
as into developing hybrid AI systems which combine the benefits of behaviour trees with
those of other approaches such as HSM.
The remainder of this paper addresses the nature and characteristics of, and suitable
applications for behaviour trees, and discusses where they might be situated in the near
future of Game AI.
Page 5 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
2. Definitions and Concepts
2.1 What are Behaviour Trees?
Behaviour Trees are simple, hierarchical data structures for managing complexity by
providing “ a graphical representation and formalization for complex actions (Markowitz,
Kider, Shoulson & Bader, 2011). They can be described as a synthesis of HSMs and
other AI techniques (Millington & Funge, 2012), such as Planning methods, especially
HTNs (Flórez-Puga, et al., 2009). They are more intuitive than state machines (Child &
Dey, 2013), and they are used to store and execute plans rather than generate them, as
is the case with HTNs (Flórez-Puga, et al., 2009). “BTs can be seen as AND-OR trees
that store all possible plans that a game entity … can follow to obtain its goals” (Flórez-
Puga, et al., 2009). It is the strict and static hierarchical nature of behaviour trees that
makes them amenable to reuse and modularization (Zhao & Szafron, 2014).
All behaviour trees are rooted tree structures that are traversed each time the AI logic is
executed (Černý, et al., 2015, Ji & Ma, 2013). Trees comprise nodes and branches in
parent-child relationships (Kirby, 2011). They can possess any number of levels, but child
nodes are restricted to a single parent (Kirby, 2011). Nodes near the root of the tree
represent higher-level behaviours that those close to the leaves (Černý, et al., 2015).
When the AI cycle runs, a parent node selects an appropriate child node to perform, with
a boolean (or still in progress) result (Johansson & Dell’Acqua, 2012) being returned from
the child to the parent (Ji & Ma, 2013). Behaviour trees can be seen as goal structures
that portray “how a high-level goal can be decomposed into lower level ones until
reaching primitive goals that can be achieved by available actions” (Rabin, 2013). Figure
5 shows a simple behaviour tree example for a non-player character (NPC) (Rabin,
2013).
Figure 5: Behaviour Tree example
As architectures, behaviour trees are unusual in that they can contain other systems
(Rabin, 2013). Each node (excepting leaf, or action nodes) is essentially a selector
making a small contribution to an overall decision (Rabin, 2013). Recent developments
have shown that a selector can contain nearly any other kind of AI approach, making
behaviour trees more than architectures; they are in fact frameworks, or meta-
architectures (Rabin, 2013).
Page 6 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
2.2 Components
Behaviour tree branches depict the relationships between nodes, which are either
composite (high level) nodes, or leaf (low level) nodes (Ji & Ma, 2013).
Leaf nodes call various functions to perform and can judge their success or not (Ji & Ma,
2013). They are depicted diagrammatically as rounded white rectangles for action or
behaviour nodes, and rounded grey rectangles for condition nodes (Johansson &
Dell’Acqua, 2012).
Composite nodes start from the top or root node, and select lower (closer to the leaves)
nodes to run (Ji & Ma, 2013).
There are several types of, or functions for, composite nodes. For example, a Priority
Selector node traverses child nodes in order, returning false only if all child nodes return
false. If one returns true, it stops the traversal and returns true to its parent node (Ji &
Ma, 2013). They are depicted as grey circles containing question marks (Johansson &
Dell’Acqua, 2012).
A Sequence Selector node traverses child nodes in order, returning true only if all child
nodes return true. If one returns false, it stops the traversal and returns false to its parent
node
(Ji & Ma, 2013). They are depicted as grey squares with arrows (Johansson &
Dell’Acqua, 2012). Selector and sequence nodes are both capable of non-linear traversal
according to weighted random variants (Ji & Ma, 2013).
A Parallel node traverses children in parallel, return a value to the parent node in
accordance with specific strategies (Ji & Ma, 2013). They are depicted as grey circles the
letter ‘P’ inside (Johansson & Dell’Acqua, 2012).
A decorator node behaves like a filter, placing constraints on execution of its (sole) child
node without altering its nature (Johansson & Dell’Acqua, 2012). They are depicted as
diamonds containing descriptive text (Johansson & Dell’Acqua, 2012).
Figure 6 shows a behaviour tree example (for a camera system), which comprises a
number of these different node types (Markowitz, et al., 2011).
Figure 6: Behaviour Tree example showing several components
Page 7 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
2.3 Types of Behaviour Trees
There are several different types, or interpretations of behaviour trees. These include
simple (or first-generation) trees which are evaluated either top down, or bottom up, as
well as more complex trees, known as second generation behaviour trees. These are
either data or event-driven (Kirby, 2011).
2.3.1 Top Down Evaluation
Most behaviour trees are evaluated top down, from root to leaf (Kirby, 2011). In this kind
of evaluation, a high level behaviour cannot decide to activate unless it is aware that at
least one child wants to activate, and this constraint holds true throughout the entire
traversal until at least one usable behaviour is identified (Kirby, 2011). Because they are
checked often in this arrangement, high-level nodes need to be fast and efficient (Kirby,
2011).
2.3.2 Bottom Up Evaluation
Some behaviour trees are evaluated from the bottom up, or from leaf to root (Kirby,
2011). This requires additional processing power, but if computation is no object, bottom
up evaluation has its advantages (Kirby, 2011). This method begins with leaves
commenting on the current state, then feed their opinions upwards, providing the higher
level nodes with absolute surety of just how much each child wants to activate, leaving
them free to prioritize available options, with final selection occurring atop the tree (Kirby,
2011). The trade off for the performance hit is the potential for better, more informed
decision-making, allowing for more nuanced behaviour variations (Kirby, 2011).
2.3.3 Second Generation Behaviour Trees
As these ‘new-fangled’ behaviour trees began to be used more in game development,
more complex instances inevitably occurred, and performance issues began to be
noticed (Champanard, 2012). These were the prime motivator for the development of
second generation behaviour trees, unveiled by Alex Champanard at a game conference
(2012). He categorized these trees as data-oriented and event-driven behaviour trees
(Champanard, 2012). Both gain performance boosts for different reasons; data-oriented
trees by improving cache coherency, and event-driven trees by minimizing the amount of
work undertaken in each traversal (Champanard, 2012). Second generation behaviour
trees are discussed further in the Advanced Topics and Trends section (4) of this paper.
2.4 Strengths & Limitations
2.4.1 Strengths
In a nutshell, the greatest strengths of the behaviour tree are both its simplicity (Rabin,
2013), and simultaneous capacity for complexity (Kirby, 2011). Behaviour trees are easy
to read and understand, even for non-programmer designers (Millington & Funge, 2012).
They are relatively easy to debug, allow for sophisticated behaviour selection, and help
manage and control complexity (Kirby, 2011). BTs are scalable and modular, and thus
reusable. They offer the flexibility to incorporate, and even improve upon (Lim,
Baumgarten & Colton, 2010), other AI methodologies “in a way that gives you full control
over behaviour and performance” (Rabin, 2013).
The composability of behaviour trees into sub-trees to handle more complex actions is a
powerful tool (Millington & Funge, 2012). Tasks share an interface (the tree), yet are
largely self-contained, and so lend themselves to hierarchies (Millington & Funge, 2012),
and extensibility (Rabin, 2013). They are free of the main constraint under which FSMs
suffer, that is they do not need to know the transition criteria for all other states (Rabin,
2013). Nor do they need to remember previously running behaviours; in fact behaviours
Page 8 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
should be independent of each other in order that the tree can be easily modified (Rabin,
2013). All these qualities make behaviour trees extremely powerful tools.
2.4.2 Limitations
Useful as they are, behaviour trees are not always the best solution for every situation
(Millington & Funge, 2012). For example, while they work well for binary decisions, things
can get complicated and cumbersome when the need arises to respond to external
events such as changing strategies based on low ammunition stocks (Millington & Funge,
2012). This is where hybrid systems come in, such as including tasks in the tree that
resemble state machines (Millington & Funge).
While behaviour trees are great at modeling what an AI can do, the fact that priority is
static means they are not always as successful at specifying what an AI should do. They
may require intimate knowledge of the world-state (Rabin, 2013), which can lead to a
plethora of dependencies on other, changing systems (Rabin, 2013). Rabin (2013) gives
an example of a case where a planning system may be more suitable than a behaviour
tree:
Since behaviors themselves are stateless, care must be taken when creating
behaviors that appear to apply memory. For example, imagine a citizen running
away from a battle. Once well away from the area, the “run away” behavior may
stop executing, and the highest-priority behavior that takes over could take the
citizen back into the combat area, making the citizen continually loop between
two behaviors. While steps can be taken to prevent this sort of problem, tradit-
ional planners can tend to deal with the situation more easily.
Additionally, since most behaviour trees traverse in full extremely often, processing
speed can sometimes be an issue when compared with FSMs (Rabin, 2013). Figure 7
shows a table summarising some of the potential strengths and limitations of behaviour
trees.
Table 1: Behaviour Trees – Summary of Potential Strengths & Limitations
Page 9 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
3. Applications
As behaviour trees become more embedded in standard game development practice,
new hybridization techniques with other systems are imagined, and new applications to
which they are suited are frequently discovered. This paper details just a few of the
established, and myriad emerging Game AI applications for behaviour trees.
3.1 Non-Player Characters
By far the most common application for which behaviour trees are utilized to date is AI for
non-player characters (NPCs) (Johansson & Dell-Acqua, 2012). Their use for controlling
basic opponent behaviours is especially common, but they can also contribute to player
immersion by guiding more complex and lifelike character behaviours (Pedica &
Vilhjálmsson, 2012).
3.1.1 Opponent AI
Opponent NPC AI generally performs three basic functions – moving NPCs, deciding
where to move, and tactical thinking (Millington & Funge, 2012), from a range of
behaviours such as attack, rest, hide, explore and patrol (Millington & Funge, 2012).
One example that both utilizes behaviour trees, and demonstrates how they can
incorporate other systems, is a military simulator ‘lifelike bots’ project (Jadon, et al, 2014).
Each behaviour tree level represents a state, with dynamic parameters calculated by
utility-based reasoners (rather than selectors) at run time (Jadon, et al., 2012).
Transitions between levels occur in accordance with a “global parameter force”, which
increases when suspicious or threat activity is present (Jadon, et al., 2014).
A relatively passive Patrol state is the default, with a traditional subtree governing
variations such as resting or chatting (Jadon, et al., 2014). When the aforementioned
force reaches a cthreshold in response to footsteps, rustling leaves, gunfire or similar,
aggressive behaviours are exhibited until the force value drops below threshold, and
patrol mode is resumed (Jadon, et al., 2014). Anytime an enemy s within NPC field of
vision, force value stops decreasing (Jadon, et al., 2014).
3.1.2 AI-controlled players
A second ‘bot’ project, this time working with the DEFCON game (real-time strategy
based on one-on-one conflict), includes an avatar feature whether an AI-controlled player
can stand in for a temporarily absent real player, as well as competitive bots to compete
against human players (Lim, Baumgarten & Colton, 2010). It applies evolutionary
algorithms to behaviour trees for individual behaviours to build a competitive NPC that,
more often not, can beat DEFCON’s existing hard-coded bot, demonstrating that
behaviour trees can successfully incorporate evolutionary techniques to develop capable
automated players (Lim, Baumgarten & Colton, 2010).
3.1.3 More complex NPC behaviours
From animals which exist as decoration or to be hunted, to fully fleshed out companion
characters, NPCs follow a “Sense-Think-Act cycle”, with the thinking part open to a broad
range of implementations (Rabin, 2013).
(i) Behaviour Objects
In Open World Games with numerous NPCs, subtrees often define behaviour
subroutines for reuse, subject to the normal limitations of behaviour trees (Černý, et al.,
2015). A project to overcome these limitations utilizes ‘Behaviour Objects’, inspired by
Object-Oriented Programming, with data and methods replaced by a brain (data and
decision logic), and behaviours (Černý et al., 2015). Behaviour executes in its context,
Page 10 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
accessing NPC internal state, whereby the NPC ‘holds’ the behaviour (Černý et al.,
2015). The behaviour can still access the object’s instance data, providing further
context and a channel of implicit communication with other NPCs exhibiting behaviour
from the same instance (Černý et al., 2015).
(ii) Emotional decision-making
Predictable, unadaptive decision-making can equal a lack of player immersion.
Johansson & Dell’Acqua tackle this issue by extending behaviour trees to incorporate
emotions into decision-making (2012). They argue that emotions “are vital for human
decision-making”, and that traditional behaviour trees that incorporate realistic emotions
into conditions would be overly-nested and cumbersome (Johansson & Dell’Acqua,
2012). They claim to solve this issue using a new type of priority selector - an emotional
selector – with dynamically evaluated priorities allowing for emotional influence
(Johansson & Dell’Acqua, 2012). The selector incorporates timing, risk perception and
planning as decision-making factors most influenced by emotion (Johansson &
Dell’Acqua, 2012). The emotional selector alters child node priorities at runtime in
response to emotions (Johansson & Dell’Acqua, 2012).
(iii) Prioritizing Behaviours
In behaviour trees most action possess a primary goal and some additional goals
depending on context (Flórez-Puga et al., 2009). Goal hierarchies that determine
behaviour based on reasoning at different levels of abstraction are crucial, since just
focusing on the primary goal can lead to artificial stupidity if, for example, reaching a
destination, even while being attacked, supersedes the need to survive (Flórez-Puga et
al., 2009). Staying alive needs to be higher up the hierarchy, so that if survival behaviour
is activated, the tree branch being executed (reach destination) can be pruned (Flórez-
Puga et al., 2009). Flórez-Puga et al. (2009) dynamically combine behaviour trees with a
Case-Based Reasoning (CBR) approach using Query Behaviour Trees (QBTs) as an
ideal midpoint between the two methodologies. The CBR system is queried at runtime,
retrieving the most appropriate behaviour from the case base of designed behaviours
(Flórez-Puga et al., 2009).
(iv) Social Territorial Intelligence
Pedica & Vilhjálmsson (2012) integrate behaviour trees with reactivity for social
territoriality in NPCs. Their system allows simultaneous running and blending of multiple
branches (Pedica & Vilhjálmsson, 2012). An arbitrational midlayer performs blending
prior to activation, and branches are prioritised in order that high priority can subsume
low priority where goals conflict (Pedica & Vilhjálmsson, 2012). They claim the result is
extensible and reusable, with responsive, smooth continuity of motion, and new levels of
social behaviour realism incorporating equality, personal distance, cohesion, and
common attention (Pedica & Vilhjálmsson, 2012).
Figure 8 shows four steps to social group dynamics. Step (a) shows a passerby is
noticed when the territory is entered, and in turn a group member notices them being
noticed. Step (b) shows the passerby invited to join the group. Step (c) shows the new
member welcomed with a glance. Step (d) shows the group making physical room for the
newcomer (Pedica & Vilhjálmsson, 2012).
Page 11 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
Figure 7: Social group dynamics simulation
Figure 9 summarises the architecture. Diagram (a) represents different action requests to
control various body parts. Diagram (b) shows the blending process, where requests are
grouped by type, combined and “packed into a motivation” (Pedica & Vilhjálmsson,
2012). Diagram (c) shows the motivation being sent to an interface for rendering action
(Pedica & Vilhjálmsson, 2012).
Figure 8: Architecture
3.2 Intelligent camera control
Camera systems for virtual worlds tend to produce fairly basic animations, when
compared with the robust storytelling features of real cinematography (Markowitz, Kider,
Shoulson & Badler, 2011). An intelligent camera system, using behaviour trees to
automatically place, aim, pan, tilt and zoom the camera, and to track events in real time,
is presented by Markowitz et al. (2011). Behaviour trees describe how an intelligent
camera might behave, “from low-level narrative elements assigned by ‘smart events’”
(Markowitz et al., 2011). Hierarchical subtrees encapsulate nodes for controlling
particular camera semantics, a modular and reusable approach capable of complexity of
style and transition (Markowitz et al., 2011). A director can optionally adjust settings in
real time (Markowitz et al., 2011).
Smart events store behaviour data (responses, parameters) and update behaviour tree
parameters, a message board updates global data for the evolving event, and a
blackboard updates local information for the behaviour tree (Markowitz et al., 2011). A
smart event broadcasts to the message board and assigns a free camera, or prioritises
events when all cameras are busy (Markowitz et al., 2011). They claim the result is “a
high-quality visual experience to the player, thereby turning the game into the visual
experience of a movie” (Markowitz et al., 2011). Figures 10 and 11 show basic camera
movement controls, and an intelligent camera behaviour tree, respectively (Markowitz et
al., 2011).
Page 12 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
Figure 9: Basic cinematography movement controls
Figure 10: An intelligent camera behaviour tree
3.3 Interactive storytelling
Automated narration tools for emergent storytelling is a growing trend, and Kapadia, Falk,
Zünd, Marti, Sumner, & Gross, 2015) present a new formalism to this purpose, called
Interactive Behaviour Trees (IBTs). Their aims are to enable designers to easily create
complex, multi-arc, branching stories in a modular and extensible way, and to allow
players more agency in their interactions within the game world (Kapadia et al., 2015).
This is achieved by decoupling player input monitoring, narrative, and player influence on
story, which facilitates both player freedom and content creation (Kapadia et al., 2015).
The behaviour trees encompass a set of tools to detect and resolve narrative
inconsistencies and conflicts, empowering the content creator to focus on the stories
rather than interactivity integration, which is automated (Kapadia et al., Feb 2015). These
tools can also dynamically detect and resolve story issues at runtime in response to
player intervention (Kapadia et al., 2015).
Page 13 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
4. Advanced Topics and Trends
4.1 Advanced Behaviour Trees
Many of the application examples seen thus far in this paper have been hybridized
examples of behaviour trees as meta-architectures, encompassing other AI architectures
in various kinds of symbiotic feedback loop, or modifying traditional nodes types. They
include utility-based reasoning (Jadon, et al., 2014), evolutionary algorithms (Lim,
Baumgarten & Colton, 2010), a kind of object-oriented state machine system (Černý et
al., 2015), an emotional variation on priority selectors (Johansson & Dell’Acqua, 2012),
case-based reasoning with query behaviour trees (Flórez-Puga et al., 2009), reactivity
with midlayer blending (Pedica & Vilhjálmsson, 2012), smart events for cinematography
(Markowitz et al., 2011), and decoupling of narrative components for modular and
emergent storytelling (Kapadia et al., Feb 2015). Some of these example can be
considered second-generation behaviour trees, which were briefly touched on earlier and
will now be discussed in slightly greater detail.
Data-oriented behaviour trees benefit from improved cache coherency (Champanard,
2012). Traditional trees access memory at many different locations (pointers), that point
to child nodes (Champanard, 2012).With scaling, this becomes a slow system
(Champanard, 2012). By pre-allocating a behaviour tree buffer and placing nodes in the
buffer, a data-oriented tree improves scalability and cache performance (Champanard,
2012).
Event-driven behaviour trees benefit from reducing the work done each time the tree is
updated (Champanard, 2012). When a node status is returned, the tree stores which
node is currently executing (Champanard, 2012). In this way it is able to return directly to
this node on the next update, avoiding the need for a full tree traversal and minimising
the tree’s workload (Champanard, 2012).
4.2 The Commercial-Academic Gap
The approximately decade-long existence of behaviour trees has coincided with both
large strides in console and PC graphics and processing power, and a subsequent
industry focus on increasing AI sophistication to match growing player expectations of the
gaming experience (Flórez-Puga et al., 2009). During this period, industry has taken
more of an interest in academic AI research “to provide rich, robust, and scalable
techniques” for NPCs, narrative schemes and, slowly, other applications (Flórez-Puga et
al., 2009). Academia has reciprocated that interest, yet a large gap still exists between
common commercial practice and cutting edge academic AI (Flórez-Puga et al., 2009),
perhaps due to a profit-motivated wariness of venturing away from tried and true
approaches (Černý et al., 2015). While it seems research areas like machine learning are
trying, without overwhelming success, to drive industry practice in new directions, Flórez-
Puga et al. (2009), when presenting their query-based, cased-based reasoning-
behaviour tree hybrid, managed to emphasise player experience without compromising
designer authorial control, a game design fundamental that industry seems unwilling to
relinquish. It will be interesting to see what the near future holds for the commercial-
academic Game AI relationship, as machine learning and data mining inevitably saturate
so many other areas of technology, and how innovative and playable forthcoming games
will be as a result.
Page 14 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
4.3 Future Trends
While it is difficult to predict exactly what even the near future will look like for Game AI
and behaviour trees, particularly in the commercial arena, it is clear that hybrid trees’
simple approach to encapsulating the inner complexities of other systems will continue to
develop, as designers and academics try and refine new combinations and ideas. It also
seems certain that the recent focus on emergent behaviour in games will continue to
influence AI, but will need to balance new developments with the high value designers
and quality controllers place on control and predictability (Kirby, 2011). Two recent
projects may provide some clue as to what kinds of developments can be expected.
Traditional behaviour trees are accessible tools for non-programming designers, yet the
hybrid forms, which utilize other approaches, can require more technical expertise to
decipher (Child & Dey, 2013). Q-Learning behaviour trees (QL-BTs) are a method for
teaching behaviour tree design via the application of reinforcement learning, developed
by Child & Dey (2013). QL-BTs facilitate the use of behaviour trees by helping designers
to identify optional execution times for each branch, and by providing tools for analysis,
debugging, and optimization for early tree prototypes (Child & Dey, 2013).
Zhao & Szafron (2014) take second-generation behaviour trees a step further by using
behaviour trees with a high level cyclic scheduler to create natural-looking behaviours by
determining general NPC objectives, and roles to satisfy those objectives. They argue
that NPCs are more convincing when, rather than just standing around when inactive,
they interact with each other in realistic ways (Zhao & Szafron, 2014). They achieve this
by creating inherently cyclical daily schedules for NPCs, adapting second-generation
trees to an explicit temporal model, to simulate the time-based ways that people organize
their activities in the real world (Zhao & Szafron, 2014).
5. Conclusion
This paper examines behaviour trees, including what they are, how they work, when they
are useful, and where they are situated within the broader field of Game AI and its
established methodologies. It provides examples of traditional, hybrid and novel
behaviour tree systems, and considers their strengths and limitations as design tools.
While acknowledging that (notwithstanding widespread use for NPC AI), not all potential
applications for behaviour trees have permeated industry to the fullest, this paper
concludes that behaviour tree research innovations will continue to influence future
commercial game development. Despite their limitations (with regard to Boolean-only
logic), behaviour trees are easy to implement and visualize, compatible with almost all
other approaches, and are eminently adaptable (Rabin, 2013). Overall, behaviour trees
have been a win for Game AI (Millington & Funge, 2012). While innovative academics
continue to experiment with their own approaches to overcoming the limitations of
behaviour trees, and use them to drive the state of the art forward, developers will, at
their own pace, continue to explore the vast potential of behaviour trees (Millington &
Funge, 2012).
Page 15 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
Figures:
Figure 1: General AI model diagram (Millington & Funge, 2012)
Figure 2: Finite State Machine Diagram (Kirby, 2011)
Figure 3: Decision-making in Game AI (Millington & Funge, 2012)
Figure 4: Decision Tree Example (Millington & Funge, 2012)
Figure 5: Behaviour Tree Example (Rabin, 2013)
Figure 6: Behaviour Tree Example Showing Several Component Types (Markowitz,
Kider, Shoulson, & Badler, 2011)
Figure 7: Social Group Dynamic Simulation (Pedica, & Vilhjálmsson, 2012)
Figure 8: Architecture (Pedica, & Vilhjálmsson, 2012)
Figure 9: Basic Cinematography Movement Controls (Markowitz et al., 2011)
Figure 10: An Intelligent Camera Behaviour Tree (Markowitz et al., 2011)
Page 16 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
Tables:
Table 1: Behaviour Trees – Summary of Potential Strengths and Limitations
Page 17 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
References:
Černý, M., Plch, T., Marko, M., Gemrot, J., Ondráček, P., & Brom, C. (2015). Using
Behavior Objects to Manage Complexity in Virtual Worlds. arXiv preprint
arXiv:1508.00377.
Champanard, A. (2012). Understanding the second-generation of behavior trees.
Tillgänglig på internet: http://aigamedev.com/insider/tutorial/second-generation-
bt.[Hämtad: 14.04. 06].
Child, C. H. T. & Dey, R. (2013). QL-BT: Enhancing Behaviour Tree Design and
Implementation with Q-Learning. 2013 IEEE Conference on Computational Intelligence
in Games (CIG), 275- 282.
Flórez-Puga, G., Gómez-Martín, M. A., Gómez-Martín, P. P., Díaz-Agudo, B., &
González-Calero, P. A. (2009). Query-enabled behavior trees. IEEE Transactions on
Computational Intelligence and AI in Games, 1(4), 298-308.
Jadon, S., Singhal, A., & Dawn, S. (2014). Military Simulator-A Case Study of Behaviour
Tree and Utility based architecture. arXiv preprint arXiv:1405.7944.
Ji, L. X., & Ma, J. H. (2014, May). Research on the Behavior of Intelligent Role in
Computer Games Based on Behavior Tree. In Applied Mechanics and Materials (Vol.
509, pp. 165-169).
Johansson, A., & Dell'Acqua, P. (2012, September). Emotional behavior trees. In
Computational Intelligence and Games (CIG), 2012 IEEE Conference on (pp. 355-362).
IEEE.
Kapadia, M., Falk, J., Zünd, F., Marti, M., Sumner, R. W., & Gross, M. (2015, February).
Computer-assisted authoring of interactive narratives. In Proceedings of the 19th
Symposium on Interactive 3D Graphics and Games, i3D (Vol. 15, pp. 85-92).
Kirby, N. (2011). Introduction to game AI. Cengage Learning Boston, MA, USA.
Lim, C. U., Baumgarten, R., & Colton, S. (2010). Evolving behaviour trees for the
commercial game DEFCON. In Applications of evolutionary computation (pp. 100-110).
Springer Berlin Heidelberg.
Markowitz, D., Kider Jr, J. T., Shoulson, A., & Badler, N. I. (2011). Intelligent camera
control using behavior trees. In Motion in Games (pp. 156-167). Springer Berlin
Heidelberg.
Millington, I., & Funge, J. (2012). Artificial intelligence for games. Morgan Kaufmann
Burlington, MA, USA.
Pedica, C., & Vilhjálmsson, H. H. (2012, August). Lifelike interactive characters with
behavior trees for social territorial intelligence. In ACM SIGGRAPH 2012 Posters (p. 32).
ACM.
Rabin, S. (Ed.). (2013). Game AI Pro: Collected Wisdom of Game AI Professionals. CRC
Press Boca Raton, FL, USA.
Page 18 of 19
A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan
*Robertson, G., & Watson, I. (2015, September). Building behavior trees from
observations in real-time strategy games. 2015 International Symposium on Innovations
in Intelligent Systems and Applications (INISTA), 1-7. IEEE.
*Shoulson, A., Garcia, F. M., Jones, M., Mead, R., & Badler, N. I. (2011). Parameterizing
behavior trees. In Motion in Games (pp. 144-155). Springer Berlin Heidelberg.
Zhao, R., & Szafron, D. (2014). Virtual Character Behavior Architecture using Cyclic
Scheduling. In Proceedings of the 9th International Conference on the Foundations of
Digital Games (FDG 2014).